from collections import defaultdict


class Trie:
    def __init__(self):
        self.nodes = {}
        self.is_word = False

    def insert(self, word):
        if not word:
            self.is_word = True
        else:
            if word[0] not in self.nodes:
                self.nodes[word[0]] = Trie()
            self.nodes[word[0]].insert(word[1:])

    def search(self, word):
        if not word:
            return self.is_word
        elif word[0] not in self.nodes:
            return False
        else:
            return self.nodes[word[0]].search(word[1:])

    def starts_with(self, word):
        if not word:
            return True
        elif word[0] not in self.nodes:
            return False
        else:
            return self.nodes[word[0]].starts_with(word[1:])

trie = Trie()
print(trie.insert("apple"))
print(trie.search("apple"))
print(trie.search("app"))
print(trie.starts_with("app"))
print(trie.insert("app"))
print(trie.search("app"))
